import java.util.Scanner;
import java.util.Stack;
import java.util.*;
public class Main {
    /*
    二叉搜索树与双向链表
     */
    public class Solution {
        TreeNode head = null;//链表头

        TreeNode pre = null;//当前遍历的前一节点

        public TreeNode Convert(TreeNode pRootOfTree) {
            if (pRootOfTree == null) {
                return null;
            }

            Convert(pRootOfTree.left);//递归左子树
            if (head == null) {//第一个结点 (头结点)
                head = pRootOfTree;
                pre = pRootOfTree;
            }else {//对接当前节点 (左中右 里的中)
                pre.right = pRootOfTree;
                pRootOfTree.left = pre;
                pre = pRootOfTree;
            }
            Convert(pRootOfTree.right);//递归右子树
            return head;
        }
    }
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;

        }

    }
    /*
     给定两个字符串 S 和 T ，判断 S 是否是 T 的子序列。
    即是否可以从 T 删除一些字符转换成 S。
     */
    public boolean isSubsequence (String S, String T) {
        // write code here
        int lenS = S.length();
        int lenT = T.length();

        int i = 0;
        int j = 0;

        while (i < lenS && j < lenT) {
            if (S.charAt(i) == T.charAt(j)) {
                i++;
                j++;
            }else {
                j++;
            }
        }
        if (i < lenS) {//如果下标i 没有走完S 则代表 T中没有S
            return false;
        }else {
            return true;
        }
    }
    /*
    描述
        输入一行字符串，分别统计出其中英文字母、空格、数字和其它字符的个数
    输入描述：
        控制台随机输入一串字符串
    输出描述：
        输出字符串中包含的英文字母个数，数字个数，空格个数，其它字符个数（格式为：英文字母x数字x空格x其他x），预设代码中已给出输出
    示例1
    输入：
        ！@#￥% asdyuihj 345678
    输出：
        英文字母8数字6空格2其他5
     */
    public static void main4(String[] args) {
        int numbers = 0;
        int words = 0;
        int space = 0;
        int other = 0;
        Scanner scanner = new Scanner(System.in);
        String str = scanner.nextLine();

        //write your code here......
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) >= 'a' && str.charAt(i) <= 'z' ||
                    str.charAt(i) >= 'A' && str.charAt(i) <= 'Z') {//字母
                words++;
            }else if (str.charAt(i) >= '0' && str.charAt(i) <= '9') {//数字
                numbers++;
            }else if (str.charAt(i) == ' ') {//空格
                space++;
            }else {//其他
                other++;
            }
        }

        System.out.println("英文字母"+words+"数字"+numbers+"空格"+space+"其他"+other);
    }
    //双端队列  首尾交替出队
    public static void main3(String[] args) {
        ArrayDeque<String> deque = new ArrayDeque<String>();

        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            String name = scanner.next();
            // 初始化队列中的数据
            deque.offerLast(name);//在尾部添加,等同于addLast()
        }

        // write your code here......
        while(true) {
            if (deque.peekFirst() == null) {//判断是否遍历完
                break;
            }else {
                System.out.println(deque.pollFirst());//弹出头一个
            }
            if (deque.peekLast() == null) {//判断是否遍历完
                break;
            }else {
                System.out.println(deque.pollLast());//弹出最后一个
            }
        }


    }
    /*
    请使用三种方式遍历一个list集合
     */
    public static void main2(String[] args) {
        Scanner scanner = new Scanner(System.in);
        List<Integer> list = new ArrayList<>();
        int num1 = scanner.nextInt();
        int num2 = scanner.nextInt();
        int num3 = scanner.nextInt();
        int num4 = scanner.nextInt();
        int num5 = scanner.nextInt();
        scanner.close();
        list.add(num1);
        list.add(num2);
        list.add(num3);
        list.add(num4);
        list.add(num5);
        System.out.print("普通for循环:");

        //write your code here......
        for (int i = 0; i < list.size(); i++) {
            System.out.print(list.get(i) + " ");
        }


        System.out.println();
        System.out.print("增强for循环:");

        //write your code here......
        for (int j : list) {
            System.out.print(j + " ");
        }

        System.out.println();
        System.out.print("迭代器遍历:");

        //write your code here......
        Iterator<Integer> it = list.listIterator();
        while(it.hasNext()) {
            System.out.print(it.next() + " ");
        }


        System.out.println();
    }
    /*
     输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。
    1. 0<=pushV.length == popV.length <=1000
    2. -1000<=pushV[i]<=1000
    3. pushV 的所有数字均不相同
     */
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param pushV int整型一维数组
     * @param popV int整型一维数组
     * @return bool布尔型
     */
    public boolean IsPopOrder (int[] pushV, int[] popV) {
        // write code here
        Stack<Integer> test = new Stack<>();

        int j = 0;
        for (int i = 0; i < pushV.length; i++) {
            test.push(pushV[i]);
            while (true) {
                if (j < popV.length && !test.isEmpty() && popV[j] == test.peek()) {//每次都循环判断是否可以出栈
                    test.pop();
                    j++;
                }else {
                    break;
                }
            }
        }
        if (!test.isEmpty()) {
            return false;
        }
        return true;
    }
    /*
     对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，
     判断其是否为回文结构。给定一个链表的头指针A，请返回一个bool值，
     代表其是否为回文结构。保证链表长度小于等于900。
     测试样例：
     1->2->2->1
     返回：true
     */
    public class PalindromeList {
        public boolean chkPalindrome(ListNode A) {
            // write code here
            if (A == null) {
                return false;
            }
            ListNode r1 = A;//每次走一步
            ListNode r2 = A;//每次走两步
            while (r2 != null && r2.next != null) {
                r1 = r1.next;
                r2 = r2.next.next;
            }

            //后半部逆置
            ListNode run = r1;
            ListNode runNext = r1.next;
            ListNode save = null;

            while (runNext != null) {
                save = runNext.next;//存储后面的,防止被释放


                runNext.next = run;//翻转


                run = runNext;//run往后走
                runNext = save;//runNext接上 下一个要翻转的
            }
            r1.next = null;//把翻转过后的 下一个置为null

            while (run != null && A != null) {
                if (run.val != A.val) {
                    return false;
                }else {
                    run = run.next;
                    A = A.next;
                }
            }
            return true;
        }
    }
    /*
    现有一链表的头指针 ListNode* pHead，
    给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，
    且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
     */
    public class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }
    public class Partition {
        public ListNode partition(ListNode pHead, int x) {
            // write code here
            if (pHead == null) {
                return null;
            }
            ListNode a = new ListNode(-1);
            ListNode aRun = a;
            ListNode b = new ListNode(-1);
            ListNode bRun = b;

            ListNode runHead = pHead;

            while (runHead != null) {
                if (runHead.val < x) {
                    aRun.next = runHead;
                    aRun = aRun.next;
                    runHead = runHead.next;
                }else {
                    bRun.next = runHead;
                    bRun = bRun.next;
                    runHead = runHead.next;
                }
            }
            if (a.next == null || b.next == null) {//小于x或大于x的没有
                return pHead;
            }
            bRun.next = null;//把最后置为null 防止循环链表
            aRun.next = b.next;
            return a.next;
        }
    }
    /*
    将一个字符串转换成一个整数，
    要求不能使用字符串转换整数的库函数。
    数值为 0 或者字符串不是一个合法的数值则返回 0
     */
    public static void main1(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String str = scanner.nextLine();
        if (str.length() == 0) {
            System.out.println(0);
        }
        int cont = 0;
        int fuhao = 1;
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == '-' && i == 0) {
                fuhao = -fuhao;
            }
            if (str.charAt(i) >= '0' && str.charAt(i) <= '9') {
                cont = cont * 10 + (str.charAt(i)-'0');
            }else if (str.charAt(i) != '+' && str.charAt(i) != '-') {
                System.out.println(0);
            }
        }
        System.out.println(cont*fuhao);
    }

}